On the algebraic structure of combinatorial problems
Identifieur interne : 002110 ( Main/Exploration ); précédent : 002109; suivant : 002111On the algebraic structure of combinatorial problems
Auteurs : Peter Jeavons [Royaume-Uni]Source :
- Theoretical Computer Science [ 0304-3975 ] ; 1998.
Abstract
We describe a general algebraic formulation for a wide range of combinatorial problems including Satisfiability, Graph Colorability and Graph Isomorphism In this formulation each problem instance is represented by a pair of relational structures, and the solutions to a given instance are homomorphisms between these relational structures. The corresponding decision problem consists of deciding whether or not any such homomorphisms exist. We then demonstrate that the complexity of solving this decision problem is determined in many cases by simple algebraic properties of the relational structures involved. This result is used to identify tractable subproblems of Satisfiability, and to provide a simple test to establish whether a given set of Boolean relations gives rise to one of these tractable subproblems.
Url:
DOI: 10.1016/S0304-3975(97)00230-2
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002B17
- to stream Istex, to step Curation: 002905
- to stream Istex, to step Checkpoint: 001614
- to stream Main, to step Merge: 002227
- to stream Main, to step Curation: 002110
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>On the algebraic structure of combinatorial problems</title><author><name sortKey="Jeavons, Peter" sort="Jeavons, Peter" uniqKey="Jeavons P" first="Peter" last="Jeavons">Peter Jeavons</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:1D1753FEF150761D3F0E8C4081BC978F5D7A126C</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1016/S0304-3975(97)00230-2</idno><idno type="url">https://api.istex.fr/document/1D1753FEF150761D3F0E8C4081BC978F5D7A126C/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">002B17</idno><idno type="wicri:Area/Istex/Curation">002905</idno><idno type="wicri:Area/Istex/Checkpoint">001614</idno><idno type="wicri:doubleKey">0304-3975:1998:Jeavons P:on:the:algebraic</idno><idno type="wicri:Area/Main/Merge">002227</idno><idno type="wicri:Area/Main/Curation">002110</idno><idno type="wicri:Area/Main/Exploration">002110</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">On the algebraic structure of combinatorial problems</title><author><name sortKey="Jeavons, Peter" sort="Jeavons, Peter" uniqKey="Jeavons P" first="Peter" last="Jeavons">Peter Jeavons</name><affiliation wicri:level="4"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX</wicri:regionArea><orgName type="university">Université de Londres</orgName><placeName><settlement type="city">Londres</settlement><region type="country">Angleterre</region><region type="région" nuts="1">Grand Londres</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation></author></analytic><monogr></monogr><series><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="ISSN">0304-3975</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1998">1998</date><biblScope unit="volume">200</biblScope><biblScope unit="issue">1–2</biblScope><biblScope unit="page" from="185">185</biblScope><biblScope unit="page" to="204">204</biblScope></imprint><idno type="ISSN">0304-3975</idno></series><idno type="istex">1D1753FEF150761D3F0E8C4081BC978F5D7A126C</idno><idno type="DOI">10.1016/S0304-3975(97)00230-2</idno><idno type="PII">S0304-3975(97)00230-2</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We describe a general algebraic formulation for a wide range of combinatorial problems including Satisfiability, Graph Colorability and Graph Isomorphism In this formulation each problem instance is represented by a pair of relational structures, and the solutions to a given instance are homomorphisms between these relational structures. The corresponding decision problem consists of deciding whether or not any such homomorphisms exist. We then demonstrate that the complexity of solving this decision problem is determined in many cases by simple algebraic properties of the relational structures involved. This result is used to identify tractable subproblems of Satisfiability, and to provide a simple test to establish whether a given set of Boolean relations gives rise to one of these tractable subproblems.</div></front></TEI><affiliations><list><country><li>Royaume-Uni</li></country><region><li>Angleterre</li><li>Grand Londres</li></region><settlement><li>Londres</li></settlement><orgName><li>Université de Londres</li></orgName></list><tree><country name="Royaume-Uni"><region name="Angleterre"><name sortKey="Jeavons, Peter" sort="Jeavons, Peter" uniqKey="Jeavons P" first="Peter" last="Jeavons">Peter Jeavons</name></region><name sortKey="Jeavons, Peter" sort="Jeavons, Peter" uniqKey="Jeavons P" first="Peter" last="Jeavons">Peter Jeavons</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002110 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002110 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:1D1753FEF150761D3F0E8C4081BC978F5D7A126C
|texte= On the algebraic structure of combinatorial problems
}}
| This area was generated with Dilib version V0.6.32. |  |